Rozpoczynał od występów w Teatrze Dramatycznym (1996-1997). Grał w Szekspirowskim "Hamlecie" w reżyserii Andrzeja Domalika (1992) i "Jak wam się podoba Szekspira" w reżyserii Piotra Cieślaka (1996) oraz w "Człowieku z La Manchy" Leigha Mitcha w reżyserii Jerzego Gruzy (1994). W 1997 roku rozpoczął współpracę z Teatrem Rozmaitości i Grzegorzem Jarzyną, który powierzył mu rolę Sydneya Price'a w swoim głośnym przedstawieniu "Bzik tropikalny" według Stanisława Ignacego Witkiewicza. Tę rolę, która przyniosła mu nagrodę na Konfrontacjach Teatralnych "Klasyka polska" w Opolu, aktor uważa za swój prawdziwy debiut.
Ta postać jest dla mnie realna, wiem, co zrobiłaby w konkretnej sytuacji, tutaj, teraz" - mówił Kosiński. - "Price jest szlachetnym geniuszem, naiwnym i jednocześnie umiejącym kochać człowiekiem.
"Rzeczpospolita" 1999, nr 95
Kosiński zagrał Price'a z ogromną werwą i ekspresją ruchową, bardzo lekko, ale jednocześnie potrafił pokazać człowieka zafrapowanego, któremu nieobcy jest filozoficzny namysł. Człowieka sztuki, który w pędzącym i coraz bardziej wynaturzającym się współczesnym świecie nie umie już znaleźć dla siebie miejsca i staje się ofiarą.
W tym samym roku wystąpił w "Historii o miłosiernej czyli testamencie psa" Ariano Suassuny w reżyserii Piotra Cieplaka. W tej religijnej przypowieści odwołującej się do tradycji łotrzykowskich historii Kosiński zagrał Chico, jak pisał Jacek Sieradzki "błazna lirycznego". Razem z Waldemarem Obłozą stworzył łobuzerski duet, który
(...) wyprowadza w pole możnych swego światka (...) Niezbyt oryginalne są te szelmostwa; reżyser z aktorami zrobił wiele, byśmy się mogli nimi dobrze bawić
Jacek Sieradzki, "Polityka" 1997, nr 665
Kilka miesięcy później Kosiński zagrał w Starym Teatrze w Krakowie postać Cyryla w "Iwonie, księżniczce Burgunda" Witolda Gombrowicza reżyserowanej przez Jarzynę. W 1998 roku ponownie współpracował z Cieplakiem, grał Anioła w sztuce "Skóra węża" Slobodana Snajdera, a w 1999 roku pracował z Krzysztofem Warlikowskim reżyserującym "Hamleta Szekspira". Zagrał Aktora. W 1999 roku wystąpił w "Magnetyzmie serca" wg Aleksandra Fredry w reżyserii Jarzyny. W tej wariacji na temat Fredrowskiej komedii, w której miłosne perypetie przenoszą się z XIX-wiecznego salonu do współczesnych mieszkań, Kosiński wcielił się w postać Albina.
Jarzynę nie interesuje tworzenie postaci wyrazistych, ale wieloznacznych" - pisała Joanna Targoń. - "To Albin (Cezary Kosiński), plączący się po scenie z coraz większymi bukietami, podsuwanymi Klarze przed oczy z milczącym wyrzutem, okazuje się nagle bardziej niż Gustaw zdobywczy.
"Gazeta Wyborcza" 12.11.2000
Kosiński uważany jest za aktora o dużej wrażliwości, którą potrafi celnie wykorzystać na scenie, doskonale operuje też ciałem.
Jego ciało układa się tak, jak on myśli - mówił Jarzyna wspominając pracę nad "Magnetyzmem serca". - Podporządkowane jest jego wrażliwości. W jego głosie mogą pojawić się fałszywe tony, ale jego ciało nigdy nie kłamie. To zmysłowy aktor, który widzi na scenie partnera, gra ze światłem i daje cień muzyce.
("Gazeta Wyborcza" 19.05.2000)
Równocześnie Kosiński grał dużo w Teatrze Telewizji. Za rolę Karlosa w "Krawcu" Sławomira Mrożka w reżyserii Michała Kwiecińskiego (1997) otrzymał wyróżnienie w Ogólnopolskim Konkursie na Wystawienie Polskiej Sztuki Współczesnej. Był też m.in. Oliverem Pankey'em w "Gwieździe sezonu" Johna Patricka w reżyserii Artura Urbańskiego (1998), w której dał popis niemal ekspresjonistycznego aktorstwa i Kapuścikiem w "Bigda idzie!" Juliusza Kadena-Bandrowskiego w reżyserii Andrzeja Wajdy (1999).
W 2000 roku Kosiński zagrał swoją najpoważniejszą rolę teatralną, tytułowego Księcia Myszkina w przedstawieniu wg "Idioty" Fiodora Dostojewskiego w reżyserii Jarzyny. Dla Kosińskiego było to doświadczenie sumujące jego dotychczasowe role sceniczne.
W Myszkinie odnajduję wiele cech postaci, które już grałem - mówił aktor. - Price jest człowiekiem szlachetnym i genialnym. Szlachetności i klasy nie można odmówić Myszkinowi. Albin jest opętany miłością, Myszkin też.
"Gazeta Wyborcza" 2000, nr 116)
Przedstawienie, jak i główna rola Kosińskiego wywołała sprzeczne opinie. O "Księciu Myszkini" pisano, że
(...) toczące się w gorączkowym i zdyszanym rytmie przedstawienie jest sugestywne i ekspresyjne, szczególnie dzięki przejmującej grze Kosińskiego i Cieleckiej
Rafał Węgrzyniak, "Odra" 2000, nr 10
Z drugiej strony zwracano uwagę, że
Owszem, Cezary Kosiński jest bardzo utalentowanym aktorem, ale akurat Myszkina grać nie powinien, bo Myszkin choć epileptyk i nawiedzony, był mimo wszystko księciem - myślę, że rosyjski książę w II połowie XIX wieku nosił się, zachowywał i wyglądał zgoła inaczej niż aktor Rozmaitości
Janusz Majcherek, "Teatr" 2000, nr 7-8
Kosińskiemu zarzucano, że swojego Myszkina ogołocił ze świadomości, a zagrał przede wszystkim biedną, schorowaną ofiarę losu.